package com.tys.algorithm.advanced.code.class16;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Code03_TopologySort {

    // directed graph and no loop
    public static List<Node> sortedTopology(Graph graph) {
        // key 某个节点  value 剩余的入度
        HashMap<Node, Integer> inMap = new HashMap<>();
        // 只有剩余入度为0的点，才进入这个队列
        Queue<Node> zeroInQueue = new LinkedList<>();
        //遍历图中所有点
        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);
            //入度为0
            if (node.in == 0) {
                //进队列
                zeroInQueue.add(node);
            }
        }
        List<Node> result = new ArrayList<>();
        //消除影响：入度为0的节点不为空
        while (!zeroInQueue.isEmpty()) {
            Node cur = zeroInQueue.poll();
            //入度为0 的节点加入结果列表
            result.add(cur);
            //遍历邻居点，将邻居点减1
            for (Node next : cur.nexts) {
                inMap.put(next, inMap.get(next) - 1);
                if (inMap.get(next) == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}
